4481. В стране невыученных уроков

 

Витя попал в страну невыученных уроков. Для того чтобы вернуться ему домой, нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа l и r, и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от l до r включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

 

Вход. Первая строка содержит количество элементов n (1 ≤ n ≤ 105) в массиве. Во второй строке находится n чисел – элементы массива ai (1 ≤ ai ≤ 109). В третьей строке находится количество запросов m (1 ≤ m ≤ 105). Далее в m строках находятся по три числа q, l, r (1 ≤ l ≤ r ≤ n).

·        Если q = 1, то требуется посчитать НОД элементов на промежутке [l, r];

·        Если q = 2, то следует заменить элемент в позиции l на число r.

 

Выход. Для каждого запроса с номером 1 в отдельной строке выведите ответ на запрос.

 

Пример входа

Пример выхода

5

2 4 6 10 8

6

1 1 5

1 2 3

2 5 15

2 3 10

1 3 5

1 1 5

2

2

5

1

 

 

РЕШЕНИЕ

дерево отрезков, единичная модификация

 

Анализ алгоритма

Для решения задачи следует реализовать дерево отрезков, поддерживающее модификацию единичного элемента и вычисление Наибольшего Общего Делителя (НОД) на отрезке.

 

Реализация алгоритма

Объявим массив SegTree для хранения дерева отрезков. Входную последовательность чисел храним в массиве v. Дерево отрезков поддерживает операцию НОД. Поскольку ai ≤ 109, то значения в ячейках  SegTree не будут выходить за границу типа int.

 

vector<int> SegTree, v;

 

По массиву а строим дерево отрезков.

 

void BuildTree(vector<int> &a, int v, int lpos, int rpos)

{

  if (lpos == rpos) SegTree[v] = a[lpos];

  else

  {

    int mid = (lpos + rpos) / 2;

    BuildTree(a, 2 * v, lpos, mid);

    BuildTree(a, 2 * v + 1, mid + 1, rpos);

    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);

  }

}

 

Функция GetGCD возвращает НОД на отрезке [left, right].

Вершине v соответствует отрезок [lpos, rpos].

 

int GetGCD(int v, int lpos, int rpos, int left, int right)

{

  if (left > right) return 0;

  if ((left == lpos) && (right == rpos)) return SegTree[v];

  int mid = (lpos + rpos) / 2;

  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),

         GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));

}

 

Функция Update присваивает элементу с индексом pos значение val.

Вершине v соответствует отрезок [lpos, rpos].

 

void update(int v, int lpos, int rpos, int pos, int val)

{

  if (lpos == rpos) SegTree[v] = val;

  else

  {

    int mid = (lpos + rpos) / 2;

    if (pos <= mid) update(2 * v, lpos, mid, pos, val);

    else update(2 * v + 1, mid + 1, rpos, pos, val);

    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);

  }

}

 

Основная часть программы. Читаем входную последовательность чисел в массив v, начиная с первого индекса.

 

scanf("%d", &n);

v.resize(n + 1);

for (i = 1; i <= n; i++)

  scanf("%d", &v[i]);

 

Строим дерево отрезков по элементам массива v[1 … n].

 

SegTree.resize(4 * n);

BuildTree(v,1,1,n);

 

Последовательно обрабатываем запросы.

 

scanf("%d",&m);

for(i = 0; i < m; i++)

{

  scanf("%d %d %d",&q,&l,&r); 

  if (q == 1) printf("%d\n",GetGCD(1,1,n,l,r));

  else update(1,1,n,l,r);

}

 

Python реализация

В списке SegTree будем хранить дерево отрезков. Реализуем дерево отрезков, которое поддерживает операцию НОД.

 

import math

 

Объявим функцию gcd, которая вычисляет НОД двух чисел.

 

def gcd(a, b):

  return math.gcd(a, b)

 

По списку а строим дерево отрезков.

 

def BuildTree(a, v, lpos, rpos):

  if lpos == rpos:

    SegTree[v] = a[lpos]

  else:

    mid = (lpos + rpos) // 2

    BuildTree(a, 2 * v, lpos, mid)

    BuildTree(a, 2 * v + 1, mid + 1, rpos)

    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

 

Функция GetGCD возвращает НОД на отрезке [left, right].

Вершине v соответствует отрезок [lpos, rpos].

 

def GetGCD(v, lpos, rpos, left, right):

  if left > right:

    return 0

  if left == lpos and right == rpos:

    return SegTree[v]

  mid = (lpos + rpos) // 2

  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),

      GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1),right))

 

Функция Update присваивает элементу с индексом pos значение val.

Вершине v соответствует отрезок [lpos, rpos].

 

def Update(v, lpos, rpos, pos, val):

  if lpos == rpos:

    SegTree[v] = val

  else:

    mid = (lpos + rpos) // 2

    if pos <= mid:

      Update(2 * v, lpos, mid, pos, val)

    else:

      Update(2 * v + 1, mid + 1, rpos, pos, val)

    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

 

Основная часть программы. Читаем входную последовательность чисел в список v, начиная с первого индекса.

 

n = int(input())

v = [0] + list(map(int, input().split()))

 

Строим дерево отрезков по элементам списка v[1 … n].

 

SegTree = [0] * (4 * n)

BuildTree(v, 1, 1, n)

 

Последовательно обрабатываем запросы.

 

m = int(input())

for _ in range(m):

  q, l, r = map(int, input().split())

  if q == 1:

    print(GetGCD(1, 1, n, l, r))

  else:

    Update(1, 1, n, l, r)